什么是模逆元

https://aaron67.cc/2020/05/30/modular-multiplicative-inverse/

整数 a 除以整数 b，若得到的余数是 r，则记作

a   m o d   b = r a \bmod{b} = r amodb=r

例如

5   m o d   3 = 2 5 \bmod{3} = 2 5mod3=2

− 5   m o d   3 = 1 -5 \bmod{3} = 1 −5mod3=1

模运算的部分性质如下：

( a + b )   m o d   c = ( ( a   m o d   c ) + ( b   m o d   c ) )   m o d   c (a + b) \bmod{c} = ((a \bmod{c}) + (b \bmod{c})) \bmod{c} (a+b)modc=((amodc)+(bmodc))modc

( a ⋅ b )   m o d   c = ( ( a   m o d   c ) ⋅ ( b   m o d   c ) )   m o d   c (a \cdot b) \bmod{c} = ((a \bmod{c}) \cdot (b \bmod{c})) \bmod{c} (a⋅b)modc=((amodc)⋅(bmodc))modc

a b   m o d   c = ( a   m o d   c ) b   m o d   c a^{b} \bmod{c} = (a \bmod{c})^{b} \bmod{c} abmodc=(amodc)bmodc

如果你对模运算还不太熟悉，推荐先阅读 Khan Academy 的入门课程。

两个整数 a、b，若它们除以正整数 n 所得的余数相等，即 a   m o d   n = b   m o d   n a \bmod{n} = b \bmod{n} amodn=bmodn，则称 a 和 b 对于模 n 同余，记作

a ≡ b ( m o d n ) a\equiv b \pmod{n} a≡b(modn)

读作 a 同余于 b 模 n，或 a 和 b 关于模 n 同余。例如

2 ≡ 8 ( m o d 6 ) 2\equiv 8 \pmod{6} 2≡8(mod6)

当 k 为整数（ k ∈ Z k \in \mathbb{Z} k∈Z）时，同余关系有如下性质。

a ≡ b ( m o d n )      ⇒      a k ≡ b k ( m o d n ) a\equiv b \pmod{n}\ \ \ \ \Rightarrow \ \ \ \ ak\equiv bk \pmod{n} a≡b(modn)    ⇒    ak≡bk(modn)

当 k、n 互质时，有

a k ≡ b k ( m o d n )      ⇒      a ≡ b ( m o d n ) ak\equiv bk \pmod{n}\ \ \ \ \Rightarrow \ \ \ \ a\equiv b \pmod{n} ak≡bk(modn)    ⇒    a≡b(modn)

参考倒数（ x y = 1 xy = 1 xy=1）的定义，对整数 a 和 b，若

a b ≡ 1 ( m o d n ) ab \equiv 1 \pmod{n} ab≡1(modn)

则称 a 和 b 关于模 n 互为模倒数，也叫模反元素或模逆元（modular multiplicative inverse），还可以记作

b ≡ 1 a ( m o d n )      或      b ≡ a − 1 ( m o d n ) b \equiv \frac{1}{a} \pmod{n}\ \ \ \ 或\ \ \ \ b \equiv a^{-1} \pmod{n} b≡a1​(modn)    或    b≡a−1(modn)

类似于实数除法，在模 n 下的除法可以用和对应模逆元的乘法来表达。”分数取模”，等价于求分母的模逆元。

当 a、b 关于模 n 互为模逆元时， b   m o d   n = 1 a   m o d   n b \bmod{n} = \frac{1}{a} \bmod{n} bmodn=a1​modn

c a   m o d   n = ( c ⋅ 1 a )   m o d   n = ( ( c   m o d   n ) ⋅ ( 1 a   m o d   n ) )   m o d   n = ( ( c   m o d   n ) ⋅ ( b   m o d   n ) )   m o d   n = ( c ⋅ b )   m o d   n \frac{c}{a} \bmod{n} = (c \cdot \frac{1}{a}) \bmod{n} = ((c \bmod{n}) \cdot (\frac{1}{a} \bmod{n})) \bmod{n} = ((c \bmod{n}) \cdot (b \bmod{n})) \bmod{n} = (c \cdot b) \bmod{n} ac​modn=(c⋅a1​)modn=((cmodn)⋅(a1​modn))modn=((cmodn)⋅(bmodn))modn=(c⋅b)modn

例如

20 3   m o d   7 = ( ( 20   m o d   7 ) ⋅ ( 1 3   m o d   7 ) )   m o d   7 = ( 6 × 5 )   m o d   7 = 2 \frac{20}{3} \bmod{7} = ((20 \bmod{7}) \cdot (\frac{1}{3} \bmod{7})) \bmod{7} = (6 \times 5) \bmod{7} = 2 320​mod7=((20mod7)⋅(31​mod7))mod7=(6×5)mod7=2

根据定义，求 a 关于模 n 的模逆元，若 b 是解， k ∈ Z k \in \mathbb{Z} k∈Z，则 b + k n b + kn b+kn 也都是解，且最小的非负整数解小于 n，例如

2 × 3 ≡ 1 ( m o d 5 ) 2 \times 3 \equiv 1 \pmod{5} 2×3≡1(mod5)

2 × 8 ≡ 1 ( m o d 5 ) 2 \times 8 \equiv 1 \pmod{5} 2×8≡1(mod5)

即 3 和 8 都是 2 关于模 5 的模逆元，其中 3 是最小的非负整数解。所以求模逆元可以通过遍历 0 ~ n 来确定。

但这种方法在 n 取值很大时效率不高。你可以参考文章 Modular multiplicative inverse，使用扩展欧几里得算法或费马小定理改进。